package kyssion.leetcode.num1_50;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
 * <p>
 * 注意：
 * <p>
 * 答案中不可以包含重复的四元组。
 * <p>
 * 示例：
 * <p>
 * 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
 * <p>
 * 满足要求的四元组集合为：
 * [
 * [-1,  0, 0, 1],
 * [-2, -1, 1, 2],
 * [-2,  0, 0, 2]
 * ]
 */
public class code18_四数之和 {
    public static void main(String[] args) {
        new code18_四数之和().fourSum(new int[]{

        }, 0);
    }

    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> listList = new ArrayList<>();
        if (nums.length < 4) {
            return listList;
        }
        Arrays.sort(nums);
        int start = 0;
        int end = 1;
        while (start < nums.length) {
            while (end < nums.length) {
                int toStart = end + 1;
                int toEnd = nums.length - 1;
                while (toStart < toEnd) {
                    int all = nums[start] + nums[end] + nums[toStart] + nums[toEnd];
                    if (all == target) {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[start]);
                        list.add(nums[end]);
                        list.add(nums[toStart]);
                        list.add(nums[toEnd]);
                        listList.add(list);
                        toEnd--;
                        while (toEnd > toStart && nums[toEnd + 1] == nums[toEnd]) {
                            toEnd--;
                        }
                    }
                    if (all > target) {
                        toEnd--;
                        while (toEnd > toStart && nums[toEnd + 1] == nums[toEnd]) {
                            toEnd--;
                        }
                    } else {
                        toStart++;
                        while (toEnd > toStart && nums[toStart - 1] == nums[toStart]) {
                            toStart++;
                        }
                    }
                }
                end++;
                while (end < nums.length && nums[end] == nums[end - 1]) {
                    end++;
                }
            }
            start++;
            while (start < nums.length && nums[start] == nums[start - 1]) {
                start++;
            }
            end = start + 1;
        }
        return listList;
    }

    /**
     * 更加深入的利用了排序的思想,看注释吧,这里反思的问题就是
     *
     * @param nums
     * @param target
     * @return
     */

    public List<List<Integer>> fourSum2(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        Arrays.sort(nums);

        for (int i = 0; i < nums.length - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            if (nums[i] + 3 * nums[nums.length - 1] < target) continue;//nums[i]+3*最大的数<target
            if (nums[i] * 3 > target) break;//mum[i]为四数最小，若4mum[i]>target,则往后的都大于target，不满足

            for (int j = i + 1; j < nums.length - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                if (nums[j] * 3 > (target - nums[i])) break;

                int low = j + 1;
                int high = nums.length - 1;
                while (low < high) {
                    int sum = nums[i] + nums[low] + nums[high] + nums[j];
                    if (sum == target) {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[low]);
                        list.add(nums[high]);
                        list.add(nums[j]);
                        result.add(list);
                        low++;
                        while (low < high && nums[low] == nums[low - 1]) low++;//int[] nums={-2,0,0,2,2}
                        high--;
                        while (high > low && nums[high] == nums[high + 1]) high--;
                    } else if (sum > target)
                        high--;
                    else if (sum < target)
                        low++;
                }
            }
        }
        return result;

    }
}
